#include <vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        //以[j][i]为结尾的子序列最大长度
        vector<vector<int>>dp(arr.size(),vector<int>(arr.size(),2));
        //因为原数组严格递增可用哈希优化
        unordered_map<int,int>u_map;
        int ans=0;
        for(int i=0;i<arr.size();i++) u_map[arr[i]]=i;
        for(int i=2;i<arr.size();i++){
            for(int j=1;j<i;j++){
                int k=arr[i]-arr[j];
                if(k<arr[j]&&u_map.count(k)) 
                    dp[j][i]=dp[u_map[k]][j]+1;
                ans=max(ans,dp[j][i]);
            }
        }
        return ans==2?0:ans;
    }
};